package pers.qianyu.month_202101.date_20210121;

import org.junit.*;

import java.util.*;

/**
 * 918. 环形子数组的最大和
 * https://leetcode-cn.com/problems/maximum-sum-circular-subarray/
 *
 * @author mizzle rain
 * @date 2021-01-21 18:01
 */
public class MaxSubarraySumCircular {
    public int maxSubarraySumCircular(int[] A) {
        int len = A.length;
        int[] nums = new int[2 * len];
        System.arraycopy(A, 0, nums, 0, len);
        System.arraycopy(A, 0, nums, len, len);
        int[] pre = new int[2 * len + 1];
        for (int i = 1; i <= len * 2; i++) pre[i] = pre[i - 1] + nums[i - 1];
        Deque<Integer> q = new LinkedList<>();
        q.addLast(0);
        int res = Integer.MIN_VALUE;
        for (int i = 1; i < len * 2 + 1; i++) {
            // 注意这里由于是前缀和所以 i - len == q.getFirst() 的时候不会越界
            if (!q.isEmpty() && i - len > q.getFirst()) q.pollFirst();
            res = Math.max(res, pre[i] - pre[q.getFirst()]);
            while (!q.isEmpty() && pre[q.getLast()] >= pre[i]) q.pollLast();
            q.addLast(i);
        }
        return res;
    }

    @Test
    public void test1() {
        int result = new MaxSubarraySumCircular().maxSubarraySumCircular(new int[]{-2, -3, -1});
        Assert.assertEquals(result, -1);
    }
}
